import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

//方法一 暴力解法
class Solution1 {
    int max=0;
    public void editVal(TreeNode root) {
        if(root==null) return;
        if(root.right!=null) {
            root.right.val = root.val * 2 + 1;
        }
        if(root.left!=null) {
            root.left.val=root.val*2;
        }
        editVal(root.right);
        editVal(root.left);
        return;
    }
    ArrayList<Integer> arrayList= new ArrayList<>();
    public void levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur.val>max) {
                max=cur.val;
            }
            arrayList.add(cur.val);
            if(cur.left!=null) {
                queue.offer(cur.left);
            }
            if(cur.right!=null) {
                queue.offer(cur.right);
            }
        }
    }
    public boolean isCompleteTree(TreeNode root) {
        root.val=1;
        editVal(root);
        levelOrder(root);
        for(int i=1;i<=max;i++) {
            if(arrayList.get(i-1)!=i) {
                return false;
            }
        }
        return true;
    }
}
public class lc958 {
}


//方法二：
class Solution2 {
    int max=0;
    int TreeNodeNum=0;
    public void editVal(TreeNode root) {
        if(root==null) return;
        TreeNodeNum++;
        if(root.val>max) {
            max=root.val;
        }
        if(root.right!=null) {
            root.right.val = root.val * 2 + 1;
        }
        if(root.left!=null) {
            root.left.val=root.val*2;
        }
        editVal(root.right);
        editVal(root.left);
        return;
    }
    public boolean isCompleteTree(TreeNode root) {
        editVal(root);
        return max==TreeNodeNum?true:false;
    }
}